larg scale graph mine backbon refin class andrea maunz christoph helma stefan kramer present approach larg scale graph mine base call backbon refin class method effici mine tree shape subgraph descriptor minimum frequenc signific constraint class fragment reduc featur set size run time class defin term fragment share common backbon method optim structur inter featur entropi oppos occurr characterist open close fragment mine experi propos method reduc featur set size gt gt compar complet tree mine open tree mine evalu crossvalid run show classif accuraci similar complet set tree significantli open tree compar open close fragment mine larg part search space prune due improv statist constraint dynam upper bound adjust confirm experi lower run time compar ordinari static upper bound prune analysi larg scale dataset yield insight import properti propos descriptor dataset coverag class size repres descriptor final cross valid run confirm descriptor render larg train set feasibl previous intract 